package sort;

import java.util.*;

/**
 * 可以参考 对k个链表进行排序  {@link divide.合并K个排序链表_23}
 */
public class 排序链表_148 {

    public static void main(String[] args) {
        ListNode h4 = new ListNode(3);
        ListNode h3 = new ListNode(1, h4);
        ListNode h2 = new ListNode(2, h3);
        ListNode h1 = new ListNode(4, h2);
        final ListNode node = sortList_merge_sort(h1);
        System.out.println();

    }



    /**
     * 可以参考 对k个链表进行排序  {@link divide.合并K个排序链表_23}
     * 归并排序
     *
     * 归并排序有递归和非递归两种  递归适合手写 因为短 非递归适合聊天 应为空间复杂度为 O(1)
     * 对比见 https://leetcode-cn.com/problems/sort-list/solution/di-gui-ban-ben-he-fei-di-gui-ban-ben-gui-tiw7/
     * TODO　非递归再写一遍
     */
    public static ListNode sortList_merge_sort(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        // ******   快慢指针法找链表中点 ******
        // 注意 1.  fast = head.next;  2. fast = fast.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 从slow右边的节点开始分裂成为两个链表  递归往下分治合并
        ListNode right = slow.next;
        slow.next = null; // 断开防止成环
        ListNode left = sortList_merge_sort(head);
        right = sortList_merge_sort(right);
        return merge2List(left, right);
    }

    public static ListNode merge2List(ListNode h1, ListNode h2){
        // 双指针  一直移动
        ListNode node = new ListNode();
        ListNode head = node;
        while (h1 != null && h2 != null) {
            if(h1.val < h2.val) {
                node.next = h1;
                h1 = h1.next;
            } else {
                node.next = h2;
                h2 = h2.next;
            }
            node = node.next;
        }
        node.next = h1 == null ? h2 : h1;
        return  head.next;
    }



    /**
     * 空间复杂度为 O(n)  不如归并排序
     */
    public ListNode sortList_heap(ListNode head) {
        if(head == null || head.next == null) return head;
        Queue<ListNode> heap= new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        while(head != null) {
            heap.offer(head);
            head = head.next;
        }
        ListNode node = heap.poll();
        ListNode dummyHead = node;
        while(!heap.isEmpty()){
            ListNode poll = heap.poll();
            node.next = poll;
            node = poll;
        }
        node.next = null; // 防止链表成环  最后一个node指针没修改
        return node;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}